package chapter02;

public class SortColors75 {
    /**
     * 改写快排
     * L=-1 小于区右边界
     * R=nums.length 大于区左边界
     * i=0
     * 1).nums[i]==1
     *  i++
     * 2).nums[i]<1
     *  i和小于区下一个数交换 右边界扩张L++ i++
     *  swap(nums,i++,++L)
     * 3).nums[i]>
     *  i和大于区下一个数交换 左边界扩张R-- i不变因为交换后的值不知道
     *  swap(nums,i,--R)
     */
    public void sortColors(int[] nums) {
        int L=-1;
        int R=nums.length;
        int i=0;
        while (i<R){
            if(nums[i]==1){
                i++;
            }else if(nums[i]<1){
                swap(nums,++L,i++);
            }else{
                swap(nums,i,--R);
            }
        }
    }

    public void swap(int[] nums,int i,int j){
        if(i==j){
            return;
        }
        nums[i]=nums[i]^nums[j];
        nums[j]=nums[i]^nums[j];
        nums[i]=nums[i]^nums[j];
    }
}
